package com.leetcode.array_matrix;

import java.time.OffsetDateTime;
import java.util.Stack;

/**
 * @author Dennis Li
 * @date 2020/10/16 16:08
 */
public class SmallestSubsequence_1081 {

    public String smallestSubsequence(String s) {
        // 256是ASCII码的数量
        int[] count = new int[256];
        char[] array = s.toCharArray();
        boolean[] inStack = new boolean[256];

        for (char c : array) {
            count[c]++;
        }
        Stack<Character> stack = new Stack<>();
        for (char c : array) {
            count[c]--;
            if (inStack[c]) continue;

            while (!stack.isEmpty() && stack.peek() > c) {
                if (count[stack.peek()] == 0)
                    break;
                inStack[stack.pop()] = false;
            }
            stack.push(c);
            inStack[c] = true;
        }

        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }

}
